1. Field of the Invention
The present invention relates generally to road design, and in particular, to a method, apparatus, and article of manufacture for determining an optimal alignment for any cleared transportation path capable of allowing a vehicle to pass.
2. Description of the Related Art
(Note: This application references a number of different publications as indicated throughout the specification by reference numbers enclosed in brackets, e.g., [x]. A list of these different publications ordered according to these reference numbers can be found below in the section entitled “References.” Each of these publications is incorporated by reference herein.)
The geometric design of a transport alignment for any cleared transportation path capable of allowing a vehicle to pass is a crucial part in civil engineering infrastructure projects and corridor planning. Once fixed, the design determines largely the construction costs, land cost, as well as future operation and maintenance costs, and environmental impact. It is therefore crucial for a planner to find an optimal transport alignment.
The geometric design of a transport alignment is traditionally done in two stages: the horizontal alignment design and the vertical profile design. The horizontal alignment is the alignment trajectory from a satellite's eye view. The vertical profile is a two dimensional view of the elevation points of the stretched-out horizontal alignment. In [17], a described method finds an optimal vertical profile for a road alignment. Embodiments of the present invention focus on a new method to find an optimal horizontal alignment for any transport path, using elements from [17].
Early attempts at horizontal alignment optimization were based on the technique of dynamic programing. In 1987, Trietsch [22] examined different types of graph data structures in combination with Dijkstra's shortest path method [7].
In 1989, Chew et. al. [6] presented a method that used a three dimensional spline model to combine horizontal and vertical highway alignments. Chew solved the model with standard nonlinear constraint optimization techniques from the calculus of variations.
A research group around Jong, Jha, and Schonfeld [13] presented a method in 2000, to optimize preliminary highway designs with genetic algorithms using data from geographic information systems (GIS).
Peter Gipps [9] published a paper in 2001, presenting parts of the method created by Quantm International, Inc. to optimize rail and road alignments. Quantm International, Inc. and its subsidiary Quantm Ltd. of Australia, were acquired in 2006 by Trimble Navigation Ltd., which offers the method as a road and railway alignment optimization software solution.
In 2003, Jong and Schonfeld [14] presented an improved method using an evolutionary model for simultaneously optimizing three-dimensional highway alignments, followed by another paper by Jha and Schonfeld [10] that includes GIS data.
Further publications in 2006 by Jha et. al. [16, 11] improved on the computational efficiency of the genetic algorithms approaches and added more cost factors like proximity, and land-use changes.
Cheng and Lee [5] used a local neighborhood heuristic to optimize three-dimensional highway alignments in 2006.
Jha and Schonfeld published a book about Intelligent Road Design [12] in 2006, outlining their genetic algorithm approach in detail.
Schonfeld and Kang experimented with different approaches using feasible gates method in 2007 [15].
Also in 2007, Lee et. al. presented their own heuristic method [19] to optimize the horizontal alignment of a highway, with a follow-up paper in 2009 [20].